Online services are an important part of modern computing infrastructure. Rather than providing hardware, software, and support for commonly used computer services, customers increasingly rely on online service providers to provide common computing services. When an online service provider provides a computing service that has access to sensitive business information from multiple customers, protecting each customer's sensitive business information becomes a difficult problem for the service provider. For example, if an online service provider provides an email service to a plurality of customers, some of which may be in competition with each other, each individual customer will demand assurances that their email is isolated from other customers. Failure to provide adequate assurances that each customer's data is protected may undermine customer confidence in the services provided by the service provider. Therefore, maintaining adequate protections for customer data is an important problem for the service provider.